package com.linzm.leetcode.mid.tree.迭代遍历;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author zimingl
 * @Date 2023/2/22 23:16
 * @Description: TODO
 */
public class Demo {
    public static void main(String[] args) {
        Demo demo = new Demo();
        List<Integer> list = demo.inOrderTraversal(TreeNode.getTree());
        System.out.println(list);
    }

    private List<Integer> preOrderTraversal(TreeNode tree) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if (tree != null) {
            stack.push(tree);
        }
        while (!stack.isEmpty()) {
            TreeNode treeNode = stack.pop();
            if (treeNode != null) {
                if (treeNode.right != null) {
                    stack.push(treeNode.right);
                }
                if (treeNode.left != null) {
                    stack.push(treeNode.left);
                }
                stack.push(treeNode);
                stack.push(null);
            } else {
                treeNode = stack.pop();
                list.add(treeNode.val);
            }
        }
        return list;
    }

    private List<Integer> inOrderTraversal(TreeNode tree) {
        if (tree == null) return null;
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(tree);
        while (!stack.isEmpty()) {
            TreeNode treeNode = stack.pop();
            if (treeNode != null) {
                if (treeNode.right != null) {
                    stack.push(treeNode.right);
                }
                stack.push(treeNode);
                stack.push(null);
                if (treeNode.left != null) {
                    stack.push(treeNode.left);
                }
            } else {
                treeNode = stack.pop();
                list.add(treeNode.val);
            }
        }
        return list;
    }

    private List<Integer> postOrderTraversal(TreeNode tree) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if (tree != null) {
            stack.push(tree);
        }
        while (!stack.isEmpty()) {
            TreeNode treeNode = stack.pop();
            if (treeNode != null) {
                stack.push(treeNode);
                stack.push(null);
                if (treeNode.right != null) {
                    stack.push(treeNode.right);
                }
                if (treeNode.left != null) {
                    stack.push(treeNode.left);
                }
            } else {
                treeNode = stack.pop();
                list.add(treeNode.val);
            }
        }
        return list;
    }
}
